package LeetCodeHot100TopInterview;

public class Q130_SurroundRegion {

    //给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，
    //找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
    //边界的不算 ==> 突破口


    //流程还是一个感染标记的过程
    public void solve(char[][] board) {
        int rLen = board.length;
        int cLen = board[0].length;
        //初始标记
        for (int i = 0; i < rLen; i++) {
            for (int i1 = 0; i1 < cLen; i1++) {
                if (board[i][i1] == 'O'){
                    boolean[] ans = new boolean[1];
                    ans[0] = true;
                    infect(board,i,i1,ans);
                    //该点代表的感染区域应该被覆盖
                    board[i][i1] = ans[0]? 'T' : 'F';
                }
            }
        }
        //覆盖
        for (int i = 0; i < rLen; i++) {
            for (int i1 = 0; i1 < cLen; i1++) {
                if (board[i][i1] == 'T' || board[i][i1] == 'F' ){
                    char c = board[i][i1];
                    board[i][i1] = '*';
                    change(board, i, i1, c);
                    //该点代表的感染区域应该被覆盖
                }
            }
        }


    }

    //感染过程 判断一个 O 所连的区域是否应该被覆盖
    //传引用是为了方便上层得到最终结果
    //这是一个标记过程
    public void infect(char[][] board, int row, int col, boolean[] ans){
        //能够到达边界代表不被包围 最终结果是 false
        if (row == -1 || row == board.length || col == -1 || col == board[0].length){
            ans[0] = false;
            return;
        }

        //上下左右去感染
        if (board[row][col] == 'O'){
            //禁止重复访问 包括上层的重复访问
            board[row][col] = '*';
            infect(board, row + 1, col, ans);
            infect(board, row - 1, col, ans);
            infect(board, row, col + 1, ans);
            infect(board, row, col - 1, ans);
        }
    }

    //修改过程
    public void change(char[][] board, int row, int col, char can){

        if (row == -1 || row == board.length || col == -1 || col == board[0].length){
            return;
        }

        //上下左右去感染
        if (board[row][col] == '*'){
            //禁止重复访问
            board[row][col] = can == 'T' ? 'X' : 'O';
            change(board, row + 1, col, can);
            change(board, row - 1, col, can);
            change(board, row, col + 1, can);
            change(board, row, col - 1, can);
        }
    }
}
